package com.arron.algorithm.leetcodetop100;

/**
 *  Leetcode 338. 比特位计数
 */
public class CountBits {



    public static void main(String[] args) {

    }


    /**
     * 暴力破解 ：时间复杂度 O(nlongn) ,空间复杂度 ： O(1)
     * @param n
     * @return
     */
    public int[] countBits(int n) {
        int[] res = new int[n+1];
        for (int i = 0; i <= n; i++) {
            int s= i;
            int k = i;
            int count = 0;
            while (k!=0){
                s = k%2;
                k = k/2;
                if (s == 1){
                    count++;
                }
            }
            res[i] = count;
        }
        return res;
    }


    /**
     *  利用奇数，偶数 的特点，
     *      奇数的二进制中1的个数始终等于前一个偶数的1的个数+1，
     *      偶数的二进制中1的个数等于右移1位后的数中1的个数
     *  时间复杂度 O(n) 空间复杂度 O(1)
     * @param n
     * @return
     */
    public int[] countBits2(int n) {
        int[] res = new int[n+1];
        res[0] = 0;
        for (int i = 1; i <=n; i++) {
            if (i%2 == 1){
                //奇数
                res[i] = res[i-1]+1;
            }else {
                //偶数
                res[i] = res[i>>1];
            }
        }
        return res;
    }


}
